CS 320 -- Midterm Study Guide

Practice Problems and Solutions 2 B

These problems are offered to help understand the lecture material and assist with completing homeworks; they will also form the basis for some problems on the midterms. They are entirely optional, and feel free to skip if you understand a concept!

You should do these problems on paper or mentally first, and only THEN check the solution.

This set of problems uses Bare-Bones Haskell, with explicit data declarations for Pairs, Triples, and Lists; here is a version of the same problems with the built-in Haskell notations for tuples and lists.

2. BareBones Haskell: Polymorphic Types and Type Checking

Suppose we have the following data declarations:

data Pair a b = P a b
data Triple a b c = T a b c
data List a = Nil | Cons a (List a)

data Either a b = Left a | Right b 
data Maybe a = Nothing | Just a

We assume that we can have Integer and Bools as defined in the Haskell Prelude. Assume for the purposes of these exercises that all arithmetic operators operate only on Integers, so pretend the type of (+) is:

 (+): Integer -> Integer -> Integer.

Therefore, all numeric types will simply be assumed to be Integer.

Give the type of the following (polymorphic) functions. Note: Assume that any numeric type is simply Integer. Also, use type variables starting with a, b, c, etc. There are no errors in these functions, all can be given a polymorphic type.

2.1.

id x = x

id :: a -> a

2.2.

select x y = x

select :: a -> b -> a

2.3.

makePair x y = P x y

makePair :: a -> b -> Pair a b

2.4.

makeSingleton x = Cons x Nil

makeSingleton :: a -> List a

2.5.

two x = P x x

two :: a -> Pair a a

2.6.

triple2Pair (T x y z) = P x (P y z)

triple2Pair :: Triple a b c -> Pair a (Pair b c)

2.7.

pair2List (P x y) = Cons x (Cons y Nil

pair2List :: Pair a a -> List a

2.8.

list2Pairs (Cons w (Cons x (Cons y (Cons z Nil)))) = (P (P w x) (P y z))

list2Pairs :: List a -> Pair (Pair a a) (Pair a a)

2.9.

safeSecond (Cons _ (Cons x _)) = Just x
safeSecond _                   = Nothing

safeSecond :: List a -> Maybe a

2.10.

checkedSecond (Cons _ (Cons x _)) = Right x
checkedSecond _                   = Left False

checkedSecond :: List a -> Either Bool a

2.11.

weirdSecond (Cons _ (Cons x _)) = Right (Just x)
weirdSecond _                   = Left Nothing

weirdSecond :: List a -> Either (Maybe b) (Maybe a)

2.12.

strangeSecond (Cons _ (Cons x _)) = Just (Right x)
strangeSecond _                   = Nothing

strangeSecond :: List a -> Maybe (Either b a)

2.13.

bizarreHead Nil               = Nothing
bizarreHead (Cons (Just x) _) = Just (Just x)

bizarreHead :: List (Maybe a) -> Maybe (Maybe a)

2.14.

repeat1 x 0 = Nil
repeat1 x n = (Cons x (repeat1 x (n-1)))

repeat1 ::a -> Integer -> List a

2.15.

repeat2 x y 0 = Nil
repeat2 x y n = (Cons x (Cons y (repeat2 x y (n-1))))

repeat2 :: a -> a -> Integer -> List a

2.16.

repeatPairs x y 0 = Nil
repeatPairs x y n = (Cons (P x y) (repeatPairs x y (n-1))

repeatPairs :: a -> b -> Integer -> List (Pair a b)

2.17.

try1 (P x y) z = (P x (P y z))

try1 :: Pair a b -> c -> Pair a (Pair b c)

2.18.

try2 (T x y z) = (P x (y z))

try2 :: Triple a (b -> c) b -> Pair a c

2.19.

try3 x y =  x ( (<4) y

try3 :: (Bool -> a) -> Integer -> a

2.20.

try4 x y z = x ((*3) y) ((`mod` z) 2)

try4 :: (Integer -> Integer -> a) -> Integer -> Integer -> a

2.21.

apply1 x y = x y

apply1 :: (a -> b) -> a -> b

2.22.

apply2 x y = x (x y)

apply2 :: (a -> a) -> a -> a

2.23.

apply3 x y z = (x y) z

apply3 :: (a -> b -> c) -> a -> b -> c

2.24.

apply4 x y z = x (y z)

apply4 :: (a -> b) -> (c -> a) -> c -> b

2.25.

apply5 x y z = x y z

apply5 :: (a -> b -> c) -> a -> b -> c

2.26.

apply6 x y z = (x z) (y z)

apply6 :: (a -> b -> c) -> (a -> b) -> a -> c

2.27.

apply7 w x y z = w (x (y z))

apply7 :: (a -> b) -> (c -> a) -> (d -> c) -> d -> b

2.28.

apply8 w x y z = ((w x) y) z

apply8 :: (a -> b -> c -> d) -> a -> b -> c -> d

2.29.

apply9 w x y z = w x y z

apply9 :: (a -> b -> c -> d) -> a -> b -> c -> d

2.30.

switch1 x y = switch1 y x    -- will not terminate, but will type check!

switch1 :: a -> a -> b

2.31.

switch2 x y z = switch2 y x z

switch2 :: a -> a -> b -> c

2.32.

switch3 x y z = switch3 z y x

switch3 :: a -> b -> a -> c

2.33.

switch4 x y z = switch4 z x y

switch4 :: a -> a -> a -> b

2.34.

lam1 = \x -> x

lam1 :: a -> a

2.35.

lam2 = \x -> (P x x)

lam2 :: a -> Pair a a

2.36.

lam3 = \x -> (T x 4 x)

lam3 :: a -> Triple a Integer a

2.37.

lam4 = \_ -> Nothing    -- You can use an anonymous variable in lambda expression!

lam4 :: a -> Maybe b

2.38.

lam5 = \x -> (P (Left x), (Just x))

lam5 :: a -> Pair (Either a b)  (Maybe a)

2.39.

lam6 = \x y -> y x

lam6 :: a -> (a -> b) -> b

2.40.

lam7 = \x -> \y -> y x

lam7 :: a -> (a -> b) -> b

2.41.

lam8 = \x -> \y -> f x y
          where f x = \x y -> (P x x)

lam8 :: a -> b -> c -> Pair b b

2.42.

lam9 x = (\y -> x y)

lam9 :: (a -> b) -> a -> b

2.43.

lam10 x y = (\z -> x (P y z))

lam10 :: (Pair a b -> c) -> a -> b -> c

2.44.

test1 = \x y -> ((\z -> x z) y)

test1 :: (a -> b) -> a -> b

2.45.

test2 x = \y -> ((\z -> x z) y)

test2 :: (a -> b) -> a -> b

2.46.

test3 x y =  (x . y) 5

test3 :: (b -> c) -> (Integer -> b) -> c

2.47.

test4 x y = ( (*3) . x) y

test4 :: (a -> Integer) -> a -> Integer

2.48.

test5 x y = (x . (*3)) y

test5 :: (Integer -> a) -> Integer -> a

2.49.

test6 = \x -> ((\y z -> y z) x 3)

test6 :: (Integer -> a) -> a

2.50.

test7 x y = x . (`f` True)
              where f x y = (P x y)

test7 :: (Pair a Bool -> b) -> c -> a -> b

End of Practice Problems 2 B.